package goleetcode

func lcaDeepestLeaves(root *TreeNode) *TreeNode {
	_, ans := recur(root)
	return ans
}

func recur(root *TreeNode) (int, *TreeNode) {
	if root == nil {
		return 0, nil
	}

	d1, lca1 := recur(root.Left)
	h2, lac2 := recur(root.Right)

	if d1 > h2 {
		return d1 + 1, lca1
	}

	if d1 < h2 {
		return h2 + 1, lac2
	}

	return d1 + 1, root
}